import java.util.*;

public class SumOf3Num {
    /*
    * 三数之和
    * 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足
    * i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。
    * 请你返回所有和为 0 且不重复的三元组。
    * 注意：答案中不可以包含重复的三元组。
    * 3 <= nums.length <= 3000
    * -10(5) <= nums[i] <= 10(5)
    * */
    public static void main(String[] args){
        SumOf3Num sumOf3Num = new SumOf3Num();
        sumOf3Num.mySolution(new int[]{-1,0,1,2,-1,-4});
    }

    // 我的想法：先把所有数和索引存入map，然后从第一个开始逐个遍历
    // 结果是没有去重，要去重有点麻烦，这题使用双指针来解题
    public List<List<Integer>> mySolution(int[] nums){
        List<List<Integer>> res = new ArrayList<>();
        Map<Integer, List<Integer>> map = new HashMap<>();
        // 存入map
        for (int i = 0; i < nums.length; i++) {
            List list = map.get(nums[i]);
            if(list==null){
                list = new ArrayList();
                map.put(nums[i], list);
            }
            list.add(i);
        }
        for (int i = 0; i <= nums.length-3; i++) {
            for (int j = i+1; j <= nums.length-2; j++) {
                int key = 0 - nums[i] - nums[j];
                List<Integer> list = map.get(key);
                if (list == null)
                    continue;
                else {
                    int finalJ = j;
                    int finalI = i;
                    list.forEach(item->{
                        if(item > finalJ){
                            List<Integer> r = new ArrayList();
                            r.add(nums[finalI]);
                            r.add(nums[finalJ]);
                            r.add(nums[item]);
                            res.add(r);
                        }
                    });
                }
            }
        }
        return res;
    }

    // 用双指针解
    public List<List<Integer>> solution(int[] nums){
        List<List<Integer>> res = new ArrayList();
        // 为什么要排序呢？因为数组中有重复的值，而且要求返回的结果是元组而不是索
        // 因此，排序不会影响最终的结果，并能为去重提供便利
        Arrays.sort(nums);
        // 开始循环，定义双指针right和left，left在最左端，right在i+1处
        // 当三者之和大于0，right左移使和减小；小于0，left右移使和变大
        // 两指针重合时，continue
        for (int i = 0; i <= nums.length-3; i++) {
            // 因为排序已完成，第一个数都大于0，则不可能有满足题意的三元组
            if (nums[i] > 0)
                return res;
            // 对i去重, 注意, 这里的判断是i == i-1 而不是i+1，
            // 这是为了避免nums只有3个数的导致找不到结果的情况[-1, -1, 2]
            if(i > 0 && nums[i] == nums[i-1])
                continue;
            int right = nums.length-1;
            int left = i+1;
            // 开始寻找元组
            while (left < right){
                int sum = nums[i] + nums[right] + nums[left];
                if(sum > 0) // 和大了，right左移
                    right--;
                else if (sum < 0) // 和小了，left右移
                    left++;
                else {
                    // 记录结果
                    ArrayList<Integer> r = new ArrayList<>
                            (Arrays.asList(nums[i], nums[left], nums[right]));
                    res.add(r);
                    // 对left和right去重
                    while (left < right && nums[left] == nums[left+1]) left++;
                    while (left < right && nums[right] == nums[right-1]) right--;

                    left++;
                    right--;
                }
            }
        }
        return res;
    }
}
